/*
  强哥的教练选择
  题目描述
    大雄教练来到了 NOI 国家队培训基地进行训练！
    这次的集训召集了国内有名的 m 位教练，共同来给 n 名同学进行集训。

    而由于教练和同学的数量过多，集训基地临时决定将大班课修改为一对一上课。
    每位同学需要先填写自己想选择的两位教练，第 i 位同学的意向教练为 ai, bi；
​    然后训练基地会依次按照编号从小到大依次给每位同学安排教练。
    安排的方式如下：
      对于第 i 位同学，
        如果他的意向教练 ai，还没有被其他同学选走，则给第 i 位同学配对 ai 教练；
        如果 ai 教练在之前已经被其他同学选择，则看他的意向教练 bi 是否被其他同学选择；
        如果他的意向教练 bi 还没有被其他同学选走，则给第 i 位同学配对 bi 教练；
        如果 bi 教练也在之前被其他同学选择，那么 i 同学只能黯然离场，无法配对教练；
      无法配对教练的同学则继续上大班课。

    现在大雄教练打算在给每位同学配对教练时提出一个问题考考他们：
      对于第 i 位同学，他需要回答的问题是：
        如果只有 i ∼ n 号同学，一共会有多少同学选到教练，成功开始上一对一课程？
  输入格式 (coach.in)
    输入第一行是两个整数 n, m，分别表示同学数量和教练数量（教练编号为 1 ∼ m）；
    接下来 n 行，每行包含两个整数 ai, bi，含义如题。
  输出格式 (coach.out)
    输出 n 行，每行包含一个整数表示第 i 个同学应该给出的答案。
  数据范围
    对于 10% 的数据，n, m ≤ 5；
    对于 30% 的数据，n, m ≤ 1000；
    对于 100% 的数据，1 ≤ n, m ≤ 100000, 1 ≤ a[i], b[i] ≤ M, a[i] 不等于 b[i]。
  样例输入1
    4 2
    1 2
    1 2
    1 2
    1 2
  样例输出1
    2
    2
    2
    1
  样例解释1
    对于 1 号同学，他需要回答的问题是 1 ∼ 4 同学依次选择教练后能配对的人数。
        1 号同学选择 1 号教练；
        2 号同学选择 2 号教练；
        3, 4 号同学的意向教练都被选走，无法配对；
      所以答案为 2。
    对于 2 号同学，他需要回答的问题是 2 ∼ 4 同学依次选择教练后能配对的人数。
        2 号同学选择 1 号教练；
        3 号同学选择 2 号教练；
        4 号同学的意向教练都被选走，无法配对；
      所以答案为 2。
    对于 3 号同学，他需要回答的问题是 3 ∼ 4 同学依次选择教练后能配对的人数。
        3 号同学选择 1 号教练；
        4 号同学选择 2 号教练；
      答案为 2。
    对于 4 号同学，他需要回答的问题是 4 ∼ 4 同学依次选择教练后能配对的人数。
        4 号同学选择 1 号教练；
      答案为 1。
*/